Various techniques have been used to model circuits and the interconnections between circuit components, otherwise referred to as a circuit interconnect. Naturally, the larger the circuit or circuit interconnect, the more complicated and time consuming it is to model these systems.
It is known to represent or re-express an original circuit model or representation using model order reduction techniques to form a smaller or reduced model or representation of the original model. For example, if an original model includes 1,000 signals, a reduced model may include, for example, 50 or 100 signals. Verification is performed by running simulations on the reduced model. Running simulations on smaller models saves time and money compared to analyzing larger, original models or representations.
The reduced models, however, should not lose important information in the original model and thus not accurately reflect the original model. Likewise, the reduced model should not be too large. While a larger reduced model may more accurately reflect the original representation, it also involves more computation and time consuming processing. Conventional systems involve tradeoffs involving the size of the reduced model, simulation time and costs, and the accuracy of a reduced model.
Another issue that arises in generating reduced models of circuits and interconnects is modeling variations, in particular, fabrication and processing variations. These variations may include thickness, width, inter-line spacing, conductivity, and local geometry effects, such as chemical-mechanical polish (CMP) induced inter-layer dielectric or metal thickness variations. For example, if a connection line on a chip is designed to have a width of 0.2 microns, the line that is actually fabricated may have a width of 0.18 microns or about 0.22 microns, or a variation of about 10%. These process variations can have significant negative effects on circuits or interconnects, particularly circuits using smaller geometries and circuits that are sensitive to such deviations, such as analog or Radio Frequency (RF) circuits. These variations can be caused by process adjustments, deviations in underlying process variables, or other unknown causes. In known systems, process variations are typically modeled as random variation in conventional modeling methods.
In one known system, interconnect modeling in a parameter variation context includes two main steps: 1. variation of unreduced circuit matrices, and 2. selecting a projection matrix, which may involve linearization and Taylor Series expansions, as discussed in further detail below.
Linearization
Linearization techniques are based on an assumption that parameter-varying matrices can be expressed as small linear deviations or perturbations from a nominal value, otherwise referred to as a “PERT” or perturbation technique. This PERT technique leads to a related model:
                                          G            ⁡                          (                                                λ                  1                                ,                …                ⁢                                                                  ,                                  λ                  M                                            )                                =                                    G              0                        +                                          ∑                k                            ⁢                              Δ                ⁢                                                                  ⁢                                  G                  k                                ⁢                                  δλ                  k                                                                    ,                              C            ⁡                          (                                                λ                  1                                ,                …                ⁢                                                                  ,                                  λ                  M                                            )                                =                                    C              0                        +                                          ∑                k                            ⁢                              Δ                ⁢                                                                  ⁢                                  C                  k                                ⁢                                                      δλ                    k                                    .                                                                                        (        5        )            
Thus, linearization and its small linear deviations can be described as using a first order linear correction of the variations or perturbations.
The choice of the projection matrix is then considered. Perturbational approaches can be used to compute projection matrices V using deviations (λ1, λ2, . . . ). For example, one technique uses the expansion to second order (without cross-terms)
                              V          ⁡                      (                                          λ                1                            ,              …              ⁢                                                          ,                              λ                M                                      )                          =                              G            0                    +                                    ∑              k                        ⁢                          Δ              ⁢                                                          ⁢                              V                k                                  (                  1                  )                                            ⁢                              δλ                k                                              +                                    ∑              k                        ⁢                          Δ              ⁢                                                          ⁢                                                                    V                    k                                          (                      2                      )                                                        ⁡                                      (                                          δλ                      k                                        )                                                  2                                                                        (        6        )            
In this approach, once the coefficients Vk(1) and Vk(2) are calculated, and the reduced model is obtained fromĜ(λ1, . . . ,λM)=V(λ1, . . . ,λM)T G(λ1, . . . ,λM)V(λ1, . . . ,λM)  (7)
by substituting equations 5 and 6 into equation 7, and dropping terms of higher than second order in the variations δ8.
One conventional technique calculates the terms in equation 6 by quadratic fitting on each coordinate. If the nominal value of each parameter is identified by λk, then for each parameter λk, the subspaces V(λ1, . . . λk+δλk, . . . δλM) and V(λ1, . . . λk−δλk, . . . δλM) are computed. The coefficients ΔVk(1)δ are obtained from a fit to these values, plus the nominal. 2M+1 Krylov spaces must be computed. If Krylov spaces of order Q are used for reduction, this procedure requires 2M+1 matrix factorizations, generates Q(2M+1) Krylov vectors, and produces a final model of size Q.
Linearization techniques, however, have a number of shortcomings. For example, linearization is not effective when using a large number of parameters. It requires too much time and, in turn, results in higher costs. Additionally, linearization is typically only accurate within a small range of values since the schemes break down for large deviations from a nominal value. Further, the assumptions that are used in linearization may not be accurate, leading to inaccurate variation modeling. Moreover, there is no indication or manner of controlling when a linearization analysis should be terminated. In other words, there is no control or indication over how much data will be collected and used to form a reduced model. Consequently, one can only guess as to when a sufficient amount of data has been obtained.
Taylor Series
Another conventional modeling approach uses multi-dimensional Taylor series expansions, otherwise referred to as tensor product moment schemes. Rather than explicitly modeling a perturbational form of projection matrices in linearization, a projection space is constructed that matches multidimensional moments. The transfer functionH(s)=LTX(s)  (8)X(s)=|sC(λ1, . . . ,λM)+G(λ1, . . . ,λM)|−1B  (9)
is expanded in polynomials of s as well as the parameters λ:X(s)=Σ(Xj,k1,k2, . . . kM)sjλ1(k1) . . . λM(kM)  (10)
A subset of the (vector) coefficients X j, k1, k2, . . . ) is used to form the Krylov space by, for example, taking expansions to second order in all parameters. Thus, this can be considered to be a generalization of the perturbation or linearization scheme and roughly corresponds to taking only the (2M +1)Q terms j=1, . . . , Q, k1, . . . , kM=(0,1)). Such generalization, however, comes at a cost.
The full space to order p with a set of n parameters includes a set
                              Q          max                      (            p            )                          =                              ∑                          k              =              0                        p                    ⁢                      (                                                            (                                      k                    +                    n                    -                    1                                    )                                !                                                              k                  !                                ⁢                                                      (                                          n                      -                      1                                        )                                    !                                                      )                                              (        11        )            
of parameters. For example, expansions to second order in four parameters require generating 15 vectors. The number of vectors that is required grows exponentially with the model order and number of parameters. The exponential growth makes generation of models of high order impractical and substantially increases computational costs. This problem also occurs in Volterra-series motivated approaches to nonlinear model reduction and is a concern that arises when forming representations for objects in higher-dimensional spaces via Cartesian product constructions.
A further shortcoming is that Taylor Series schemes retain all the Qmax(p) vectors X j, k1, k2, . . . for construction of the final model. This leads to a larger model of size Qmax(p) instead of a smaller size p. Further, for a given problem, both linearization and Taylor Series methods cannot be candidates. If the PERT method is sufficiently accurate, there is no need to use the TP-M scheme, but the TP-M method must be adopted when the PERT method is inaccurate. There does not, however, appear to be a good method of determining the accuracy of either scheme.
Accordingly, there exists a need for a circuit or circuit interconnect modeling technique that provides accurate and optimally sized interconnect models that account for variations by providing an indication as to when a sufficient amount of data has been obtained, improving upon the shortcomings of prior reduction techniques.